#include <iostream>
using namespace std;

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

ListNode *reverseBetween(ListNode *head, int m, int n) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(!head)
		return NULL;
	// dummy head
	ListNode *newHead = new ListNode(0);
	newHead->next = head;
	// walk to m
	int iCur = 1;
	ListNode *pPre = newHead;
	ListNode *pCur = head;
	while(iCur<m){
		pPre = pCur;
		pCur = pCur->next;
		++iCur;
	}
	// now pCur points to mth
	ListNode *pmPre = pPre;
	ListNode *pm = pCur;
	pPre = pCur;
	pCur = pCur->next;
	++iCur;
	while(iCur<=n){
		ListNode *pNext = pCur->next;
		pCur->next = pPre;
		pPre = pCur;
		pCur = pNext;
		++iCur;
	}
	// now pCur points to n+1 th, pPre points to n
	pm->next = pCur;
	pmPre->next = pPre;

	ListNode *res = newHead->next;
	delete newHead;
	return res;
}

int main(){
	return 0;
}